package leetcode

import (
	"container/heap"
	"sort"
)

// scheduleCourse 函数旨在找出一个人可以完成的最大课程数。
// 课程由一个整数数组表示，其中每个子数组包含两个整数，分别代表课程的持续时间和最后期限。
// 该函数通过贪心算法结合优先队列（最大堆）来实现，优先选择持续时间短的课程，并在必要时替换掉堆顶的最长课程。
// 参数 courses 是一个二维整数数组，每个子数组包含两个元素，分别表示课程的持续时间和最后期限。
// 返回值是这个人可以完成的最大课程数。
func scheduleCourse(courses [][]int) int {
	// 对课程按照最后期限进行升序排序，以便优先考虑最后期限早的课程。
	sort.Slice(courses, func(i, j int) bool {
		return courses[i][1] < courses[j][1]
	})

	// 初始化一个最大堆，用于存储已选择课程的持续时间。
	h := &Heap{}
	// 初始化总学习时间为0。
	time := 0

	// 遍历每个课程。
	for _, course := range courses {
		// 获取课程的持续时间。
		duration := course[0]
		// 如果学习该课程后，总时间不超过该课程的最后期限，则加入最大堆，并更新总时间。
		if time+duration <= course[1] {
			heap.Push(h, duration)
			time += duration
		} else {
			// 如果堆不为空且堆顶元素大于当前课程的持续时间，则移除堆顶元素（最长课程），加入当前课程，并更新总时间。
			if h.Len() > 0 && h.Peek().(int) > duration {
				time -= heap.Pop(h).(int)
				heap.Push(h, duration)
				time += duration
			}
		}
	}
	// 返回最大堆的大小，即可以完成的最大课程数。
	return h.Len()
}

// Heap 是一个实现了heap.Interface的最大堆。
type Heap []int

// Len 返回堆中元素的数量。
func (h Heap) Len() int { return len(h) }

// Less 比较两个元素的大小，用于维护最大堆的性质。
func (h Heap) Less(i, j int) bool { return h[j] < h[i] }

// Swap 交换两个元素的位置，用于维护堆的结构。
func (h Heap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }

// Push 向堆中添加一个新元素。
func (h *Heap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

// Pop 从堆中移除并返回堆顶元素。
func (h *Heap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

// Peek 返回堆顶元素但不移除它。
func (h *Heap) Peek() interface{} {
	return (*h)[0]
}
